package com.lun.swordtowardoffer2.c13;

import java.util.ArrayList;
import java.util.List;

public class Subsets {
	//回溯算法
	public List<List<Integer>> subsets(int[] nums) {
		List<List<Integer>> result = new ArrayList<>();
		List<Integer> path = new ArrayList<>();
		backtracking(path, nums, 0, result);
		return result;
	}

	private void backtracking(List<Integer> path, int[] originalArray, int startIndex, List<List<Integer>> result) {
		result.add(new ArrayList<>(path));

		//本if语块可以移除
		if(startIndex == originalArray.length) {
			return;
		}

		for (int i = startIndex; i < originalArray.length; i++) {
			path.add(originalArray[i]);
			backtracking(path, originalArray, i + 1, result);
			path.remove(path.size() - 1);
		}
	}
}
